For this homework, there is no starter file. You have to create your own .py file and submit it to Autolab. You can take a previous starter file and modify it appropriately.
Please add your name, Andrew id, and section at the top of the file.
Write test functions for each function you write.
APPLY TOP-DOWN DESIGN, USE LOTS OF HELPER FUNCTIONS.
IMPORTANT: Make sure you put all test functions and manually graded functions below #ignore_rest.
You will be graded on style. You can lose up to 10 poins for style (out of 100 points). Please see here for the style rubric.
You may not use recursion or any other constructs that we have not yet covered in class.
You will have 4 submissions on Autolab for this homework.
Questions
1. Better Big Oh [30 pts][manually graded]
In the last week's homework
3.3
you analyzed the big-Oh of 5 separate functions. Your job now is to:
- Provide an equivalent Python function that is more than a constant-factor faster (so it's worst-case big-oh runtime is in a different function family). The better your solution's big-oh runtime, the more points you get!
- State and prove (in a few words) your better solution's worst-case big-oh runtime.
In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise.
import copy
def slow1(a):
(b, c) = (copy.copy(a), 0)
while (b != [ ]):
b.pop()
c += 1
return c
def slow2(a):
n = len(a)
count = 0
for i in range(n):
for j in range(n):
if (a[i] == a[j]):
count += 1
return (count == n)
def slow3(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = 0
for c in b:
if c not in a:
result += 1
return result
def slow4(a, b):
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta > result):
result = delta
return result
def slow5(a, b):
# Hint: this is a tricky one! Even though it looks syntactically
# almost identical to the previous problem, in fact the solution
# is very different and more complicated.
# You'll want to sort one of the lists,
# and then use binary search over that sorted list (for each value in
# the other list). In fact, you should use bisect.bisect for this
# (you can read about this function in the online Python documentation).
# The bisect function returns the index i at which you would insert the
# value to keep the list sorted (with a couple edge cases to consider, such
# as if the value is less than or greater than all the values in the list,
# or if the value actually occurs in the list).
# The rest is left to you...
#
# assume a and b are the same length n
n = len(a)
assert(n == len(b))
result = abs(a[0] - b[0])
for c in a:
for d in b:
delta = abs(c - d)
if (delta < result):
result = delta
return result
2. invertDictionary(d) [20 pts][autograded]
See question 3 from
here.
3. friendsOfFriends(d)[20 pts][autograded]
See question 5 from
here.
4. runFancyWheel(d)[30 pts][manually graded]
See
this file for this question.
Note Your top level function should be runFancyWheel(), with no parameters. That's what we will call to test your function and you will loose points if that is not the name of your top level function.
here.
